home *** CD-ROM | disk | FTP | other *** search
/ AGA Toolkit '97 / The AGA Toolkit '97.iso / miscellaneous / science / maths / calc / source / alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-07  |  13.2 KB  |  611 lines
  1. /*
  2.  * Copyright (c) 1994 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Description:
  7.  *    This is a very fast storage allocator. It allocates blocks of a small
  8.  *    number of different sizes, and keeps free lists of each size.  Blocks
  9.  *    that don't exactly fit are passed up to the next larger size.  In this
  10.  *    implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  11.  *    This is designed for use in a program that uses vast quantities of
  12.  *    memory, but bombs when it runs out.
  13.  *
  14.  * Abnormal Conditions
  15.  *    This is a public domain storage allocator.
  16.  *
  17.  * Modifications:
  18.  *    Date        Programmer        Description of modification
  19.  *    27-FEB-90    Landon Curt Noll    most systems can ignore alloc.c
  20.  *    2-OCT-89    David I. Bell        Add free list. Sbrk now optional
  21.  *    30-JUN-87    Peter Miller        Made it work on Slimos.
  22.  *    21-FEB-82    Chris Kingsley        Initial Coding
  23.  *            kingsley@cit-20        Caltech
  24.  */
  25.  
  26. #include <stdio.h>
  27. #include "alloc.h"
  28. #include "have_stdlib.h"
  29.  
  30. #ifdef HAVE_STDLIB_H
  31. # include <stdlib.h>  /* AMIGA: substituted stdlib.h for malloc.h */
  32. #endif
  33.  
  34. #if 0
  35. #define DEBUG    1        /* defined if debugging code enabled */
  36. #define MSTATS    1        /* defined if memory statistics kept */
  37. #endif
  38. #define    NO_SBRK    1        /* defined if cannot use sbrk */
  39.  
  40.  
  41. #if defined(CALC_MALLOC)
  42. /*
  43.  * Make these functions really accessible here.
  44.  */
  45. #undef    malloc
  46. #undef    realloc
  47. #undef    free
  48.  
  49.  
  50. #ifdef DEBUG
  51. #define assert(x,v) if ((x)==0) assertfailed(v)
  52. #else
  53. #define assert(x,v)
  54. #endif
  55.  
  56. typedef unsigned char u_char;
  57. typedef unsigned short u_short;
  58. typedef unsigned int u_int;
  59. typedef char * caddr_t;
  60.  
  61. #ifdef NO_SBRK
  62. extern char * malloc();
  63. extern char * realloc();
  64. #else
  65. extern char * sbrk();
  66. #endif
  67.  
  68.  
  69. /*
  70.  * The overhead on a block is at least 4 bytes.  When free, this space
  71.  * contains a pointer to the next free block, and the bottom two bits must
  72.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  73.  * byte is the size index.  The remaining bytes are for alignment.
  74.  * If range checking (RCHECK) is enabled and the size of the block fits
  75.  * in two bytes, then the top two bytes hold the size of the requested block
  76.  * plus the range checking words, and the header word MINUS ONE.
  77.  */
  78.  
  79. union overhead
  80. {
  81.     union overhead * ov_next;    /* when free */
  82.     struct
  83.     {
  84.         u_char ovu_magic;    /* magic number */
  85.         u_char ovu_index;    /* bucket # */
  86. #define ov_magic ovu.ovu_magic
  87. #define ov_index ovu.ovu_index
  88. #ifdef RCHECK
  89.         u_short ovu_size;    /* actual block size */
  90.         u_int ovu_rmagic;    /* range magic number */
  91. #define ov_size ovu.ovu_size
  92. #define ov_rmagic ovu.ovu_rmagic
  93. #endif
  94.     } ovu;
  95. };
  96.  
  97. #define QUANTUM_NBITS    4
  98. #define QUANTUM        (1<<QUANTUM_NBITS)
  99.  
  100. #define MAGIC    0xff        /* magic # on accounting info */
  101. #define RMAGIC    0x55555555    /* magic # on range info */
  102. #ifdef RCHECK
  103. #define RSLOP    sizeof(u_int)
  104. #else
  105. #define RSLOP    0
  106. #endif
  107.  
  108. /*
  109.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  110.  * smallest allocatable block is 8 bytes.  The overhead information
  111.  * precedes the data area returned to the user.
  112.  */
  113.  
  114. #define NBUCKETS    32    /* we can't run out on a 32 bit machine! */
  115. static union overhead * nextf[NBUCKETS];
  116. static union overhead *watchloc = 0;    /* location to be watched */
  117.  
  118. #ifdef MSTATS
  119.  
  120. /*
  121.  * nmalloc[i] is the difference between the number of mallocs and frees
  122.  * for a given block size.
  123.  */
  124.  
  125. static u_int nmalloc[NBUCKETS];
  126.  
  127. #endif
  128.  
  129.  
  130. /*
  131.  * Watch some allocated memory to see if it gets blasted.
  132.  */
  133. allocwatch(cp)
  134.     char *cp;
  135. {
  136.     if (cp == NULL) {
  137.         watchloc = NULL;
  138.         return;
  139.     }
  140.     watchloc = (union overhead *)cp - 1;
  141.     assert(watchloc->ov_magic == MAGIC, 10);
  142. }
  143.  
  144.  
  145. alloccheck()
  146. {
  147.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 11);
  148. }
  149.  
  150.  
  151. /*
  152.  * NAME
  153.  *    morecore - get more memory
  154.  *
  155.  * SYNOPSIS
  156.  *    void
  157.  *    morecore(bucket)
  158.  *    int bucket;
  159.  *
  160.  * DESCRIPTION
  161.  *    Morecore is used to allocate more memory to the indicated bucket.
  162.  *
  163.  * RETURNS
  164.  *    void
  165.  */
  166. static void
  167. morecore(bucket)
  168.     register u_int    bucket;
  169. {
  170.     register union overhead * op;
  171.     register u_int    rnu;    /* 2^rnu bytes will be requested */
  172.     register u_int    nblks;    /* become nblks blocks of the desired size */
  173.     register u_int    siz;
  174.  
  175.     assert(bucket >= QUANTUM_NBITS, 1);
  176.     assert(bucket < NBUCKETS, 2);
  177.     assert(!nextf[bucket], 3);
  178. #ifndef NO_SBRK
  179.     /*
  180.      * Insure memory is allocated on a page boundary.
  181.      * Should make getpageize() call?
  182.      */
  183. #define PAGE_SIZE (1<<10)
  184.     siz = (u_int)sbrk(0);
  185.     if(siz & (PAGE_SIZE-1))
  186.         sbrk(PAGE_SIZE - (siz & (PAGE_SIZE-1)));
  187. #endif
  188.  
  189.     /* take 2k unless the block is bigger than that */
  190.     rnu = (bucket <= 11) ? 11 : bucket;
  191.     assert(rnu >= bucket, 4);
  192.     nblks = 1L << (rnu - bucket); /* how many blocks to get */
  193.     siz = 1L << rnu;
  194.  
  195. #ifndef NO_SBRK
  196.     op = (union overhead *)sbrk(siz);
  197.     /* no more room! */
  198.     if ((int)op == -1)
  199.         return;
  200.     /*
  201.      * Round up to minimum allocation size boundary
  202.      * and deduct from block count to reflect.
  203.      */
  204.     if((int)op & (QUANTUM-1))
  205.     {
  206.         op = (union overhead *)(((int)op + QUANTUM) &~ (QUANTUM-1));
  207.         nblks--;
  208.     }
  209. #else
  210.     op = (union overhead *)malloc(siz);
  211.     /* no more room! */
  212.     if (!op)
  213.         return;
  214. #endif
  215.     /*
  216.      * Add new memory allocated to the
  217.      * free list for this hash bucket.
  218.      */
  219.     nextf[bucket] = op;
  220.     siz = 1L << bucket;
  221.     while (--nblks)
  222.     {
  223.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  224.         op = op->ov_next;
  225.     }
  226. }
  227.  
  228.  
  229. /*
  230.  * NAME
  231.  *    mem_alloc - memory allocator
  232.  *
  233.  * SYNOPSIS
  234.  *    char *
  235.  *    mem_alloc()
  236.  *
  237.  * DESCRIPTION
  238.  *    Mem_alloc is used to allocate memory large enought to fit the requested
  239.  *    size, and on a boundary suitable for placing any value.
  240.  *
  241.  * RETURNS
  242.  *    char *, pointer to base of dynamic memory allocated
  243.  *
  244.  * CAVEAT
  245.  *    Use mem_free() when you are finished with the space.
  246.  */
  247. char *
  248. mem_alloc(nbytes)
  249.     register unsigned long int nbytes;
  250. {
  251.     register union overhead *p;
  252.     register int    bucket;
  253.     register unsigned long int shiftr;
  254.  
  255.     if (nbytes > ((unsigned int) -1))
  256.         return NULL;
  257.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 12);
  258.     /*
  259.      * Convert amount of memory requested into
  260.      * closest block size stored in hash buckets
  261.      * which satisfies request.  Account for
  262.      * space used per block for accounting.
  263.      */
  264.     nbytes = (nbytes + sizeof (union overhead) + RSLOP + (QUANTUM-1)) &~ (QUANTUM-1);
  265.     shiftr = (nbytes - 1) >> QUANTUM_NBITS;
  266.     /* apart from this loop, this is O(1) */
  267.     bucket = QUANTUM_NBITS;
  268.     while(shiftr)
  269.     {
  270.         shiftr >>= 1;
  271.         bucket++;
  272.     }
  273.  
  274.     /*
  275.      * If nothing in hash bucket right now,
  276.      * request more memory from the system.
  277.      */
  278.     if (!nextf[bucket])
  279.         morecore(bucket);
  280.     if (!(p = nextf[bucket]))
  281.         return (char*)0;
  282.     /* remove from linked list */
  283.     nextf[bucket] = p->ov_next;
  284.     p->ov_magic = MAGIC;
  285.     p->ov_index = bucket;
  286. #ifdef MSTATS
  287.     nmalloc[bucket]++;
  288. #endif
  289. #ifdef RCHECK
  290.     /*
  291.      * Record allocated size of block and
  292.      * bound space with magic numbers
  293.      */
  294.     if (nbytes <= (1L<<16))
  295.         p->ov_size = nbytes - 1;
  296.     p->ov_rmagic = RMAGIC;
  297.     *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  298. #endif
  299.     return ((char *)(p + 1));
  300. }
  301.  
  302.  
  303. /*
  304.  * NAME
  305.  *    mem_free - free memory
  306.  *
  307.  * SYNOPSIS
  308.  *    int
  309.  *    mem_free(cp)
  310.  *    char * cp;
  311.  *
  312.  * DESCRIPTION
  313.  *    Mem_free is used to release space allocated by mem_alloc
  314.  *    or mem_realloc.
  315.  *
  316.  * RETURNS
  317.  *    int
  318.  *
  319.  * CAVEAT
  320.  *    do not pass mem_free() an argument that was returned by mem_alloc()
  321.  *    or mem_realloc().
  322.  */
  323. int
  324. mem_free(cp)
  325.     char *    cp;
  326. {
  327.     register u_int    bucket;
  328.     register union overhead *op;
  329.  
  330.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 13);
  331.     if (!cp)
  332.         return;
  333.     op = (union overhead *)cp - 1;
  334.     assert(op->ov_magic == MAGIC, 5);    /* make sure it was in use */
  335.     assert(op->ov_index < NBUCKETS, 6);
  336.     assert(op->ov_index >= QUANTUM_NBITS, 7);
  337. #ifdef RCHECK
  338.     assert(op->ov_index > 16 || op->ov_size == (1L<<op->ov_index)-1, 8);
  339.     assert(op->ov_rmagic == RMAGIC, 9);
  340.     assert(op->ov_index > 16 || *(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC, 10);
  341. #endif
  342. #ifndef DEBUG
  343.     if(op->ov_magic != MAGIC)
  344.         return;        /* sanity */
  345. #endif
  346.     bucket = op->ov_index;
  347.     op->ov_next = nextf[bucket];
  348.     nextf[bucket] = op;
  349. #ifdef MSTATS
  350.     nmalloc[bucket]--;
  351. #endif
  352. }
  353.  
  354.  
  355. /*
  356.  * NAME
  357.  *    findbucket - find a bucket
  358.  *
  359.  * SYNOPSIS
  360.  *    int
  361.  *    findbucket(freep, srchlen)
  362.  *    union overhead * freep;
  363.  *    int srchlen;
  364.  *
  365.  * DESCRIPTION
  366.  *    Findbucket is used to find the bucket a free block is in.
  367.  *    Search ``srchlen'' elements of each free list for a block whose
  368.  *    header starts at ``freep''.  If srchlen is -1 search the whole list.
  369.  *
  370.  * RETURNS
  371.  *    bucket number, or -1 if not found.
  372.  */
  373. static int
  374. findbucket(freep, srchlen)
  375.     union overhead *    freep;
  376.     int    srchlen;
  377. {
  378.     register union overhead *p;
  379.     register int    i, j;
  380.  
  381.     for (i = 0; i < NBUCKETS; i++)
  382.     {
  383.         j = 0;
  384.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next)
  385.         {
  386.             if (p == freep)
  387.                 return i;
  388.             j++;
  389.         }
  390.     }
  391.     return -1;
  392. }
  393.  
  394.  
  395. /*
  396.  * When a program attempts "storage compaction" as mentioned in the
  397.  * old malloc man page, it realloc's an already freed block.  Usually
  398.  * this is the last block it freed; occasionally it might be farther
  399.  * back.  We have to search all the free lists for the block in order
  400.  * to determine its bucket: first we make one pass thru the lists
  401.  * checking only the first block in each; if that fails we search
  402.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  403.  * is extern so the caller can modify it).  If that fails we just copy
  404.  * however many bytes was given to realloc() and hope it's not huge.
  405.  */
  406.  
  407. static int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  408.  
  409. /*
  410.  * NAME
  411.  *    mem_realloc - change size
  412.  *
  413.  * SYNOPSIS
  414.  *    char
  415.  *    mem_realloc(cp, nbytes)
  416.  *    char * cp;
  417.  *    u_int nbytes;
  418.  *
  419.  * DESCRIPTION
  420.  *    Mem_realloc is used to enlarge a chunk of memory
  421.  *    returned by mem_alloc() or mem_realloc().
  422.  *
  423.  * RETURNS
  424.  *    char *, pointer to base of dynamic memory allocated
  425.  *
  426.  * CAVEAT
  427.  *    Use mem_free() when you are finished with the space.
  428.  */
  429. char *
  430. mem_realloc(cp, nbytes)
  431.     char *cp;
  432.     unsigned long    nbytes;
  433. {
  434.     register u_int    old_nbytes;
  435.     register union overhead *op;
  436.     char *    res;
  437.     register u_int    old_bucket;
  438.     short    was_alloced = 0;
  439.  
  440.     if (nbytes > ((unsigned int) -1))
  441.         return NULL;
  442.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 14);
  443.     if (!cp)
  444.         return mem_alloc(nbytes);
  445.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  446.     if (op->ov_magic == MAGIC)
  447.     {
  448.         was_alloced++;
  449.         old_bucket = op->ov_index;
  450.     }
  451.     else
  452.     {
  453.         /*
  454.          * Already free, doing "compaction".
  455.          *
  456.          * Search for the old block of memory on the
  457.          * free list. First, check the most common
  458.          * case (last element free'd), then (this failing)
  459.          * the last ``realloc_srchlen'' items free'd.
  460.          * If all lookups fail, then assume the size of
  461.          * the memory block being realloc'd is the
  462.          * smallest possible.
  463.          */
  464.         if
  465.         (
  466.             (old_bucket = findbucket(op, 1)) == -1
  467.         &&
  468.             (old_bucket = findbucket(op, realloc_srchlen)) == -1
  469.         )
  470.             old_bucket = QUANTUM_NBITS;
  471.     }
  472.     old_nbytes = (1L << old_bucket) - sizeof(union overhead) - RSLOP;
  473.  
  474.     /*
  475.      * avoid the copy if same size block
  476.      */
  477.     if
  478.     (
  479.         was_alloced
  480.     &&
  481.         nbytes <= old_nbytes
  482.     &&
  483.         nbytes > (old_nbytes >> 1) - sizeof(union overhead) - RSLOP
  484.     )
  485.         return cp;
  486.  
  487.     /*
  488.      * grab another chunk
  489.      */
  490.     if(!(res = mem_alloc(nbytes)))
  491.         return (char*)0;
  492.     assert(cp != res, 11);
  493.     memcpy(res, cp, (nbytes < old_nbytes) ? nbytes : old_nbytes);
  494.     if(was_alloced)
  495.         mem_free(cp);
  496.     return res;
  497. }
  498.  
  499. #else /*CALC_MALLOC*/
  500.  
  501. #undef MSTATS
  502.  
  503. #endif /*CALC_MALLOC*/
  504.  
  505.  
  506.  
  507. /*
  508.  * Allocate a new item from the specified free list.
  509.  * Returns NULL if no item can be allocated.
  510.  */
  511. ALLOCITEM *
  512. allocitem(fp)
  513.     FREELIST *fp;        /* free list header */
  514. {
  515.     FREEITEM *ip;        /* allocated item */
  516.  
  517.     if (fp->curfree > 0) {
  518.         fp->curfree--;
  519.         ip = fp->freelist;
  520.         fp->freelist = ip->next;
  521.         return (ALLOCITEM *) ip;
  522.     }
  523.     ip = (FREEITEM *) malloc(fp->itemsize);
  524.     if (ip == NULL)
  525.         return NULL;
  526.     return (ALLOCITEM *) ip;
  527. }
  528.  
  529.  
  530. /*
  531.  * Free an item by placing it back on a free list.
  532.  * If too many items are on the list, it is really freed.
  533.  */
  534. void
  535. freeitem(fp, ip)
  536.     FREELIST *fp;        /* freelist header */
  537.     FREEITEM *ip;        /* item to be freed */
  538. {
  539.     if (ip == NULL)
  540.         return;
  541.     if (fp->curfree >= fp->maxfree) {
  542.         free((char *) ip);
  543.         return;
  544.     }
  545.     ip->next = fp->freelist;
  546.     fp->freelist = ip;
  547.     fp->curfree++;
  548. }
  549.  
  550.  
  551. /*
  552.  * NAME
  553.  *    mem_stats - print memory statistics
  554.  *
  555.  * SYNOPSIS
  556.  *    void
  557.  *    mem_stats(s)
  558.  *    char * s;
  559.  *
  560.  * DESCRIPTION
  561.  *    Mem_stats is used to print out statistics about current memory usage.
  562.  *    ``s'' is the title string
  563.  *
  564.  *    Prints two lines of numbers, one showing the length of the free list
  565.  *    for each size category, the second showing the number of mallocs -
  566.  *    frees for each size category.
  567.  *
  568.  * RETURNS
  569.  *    void
  570.  */
  571. /*ARGSUSED*/
  572. void
  573. mem_stats(s)
  574.     char *    s;
  575. {
  576. #ifdef MSTATS
  577.     register int    i, j;
  578.     register union overhead *p;
  579.     int    totfree = 0;
  580.     int    totused = 0;
  581.  
  582.     fprintf(stderr, "Memory allocation statistics %s\n", s);
  583.     fprintf(stderr, "%11s:%12s%12s%12s\n", "Bucket", "In Use", "Free", "Sum");
  584.     for (i = 0; i < NBUCKETS; i++)
  585.     {
  586.         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  587.             ;
  588.         if(!j && !nmalloc[i])
  589.             continue;
  590.         fprintf(stderr, "%11d:%12d%12d%12d\n", (1L<<i), nmalloc[i], j, j+nmalloc[i]);
  591.         totfree += j * (1L << i);
  592.         totused += nmalloc[i] * (1L << i);
  593.     }
  594.     fprintf(stderr, "%11s:%12d%12d%12d\n", "Totals", totused, totfree, totused+totfree);
  595. #else
  596.     fprintf(stderr, 
  597.         "Memory allocation stats were not compiled into calc\n");
  598. #endif
  599. }
  600.  
  601. #ifdef DEBUG
  602. void
  603. assertfailed(n)
  604. {
  605.     printf("Assertion %d failed\n", n);
  606.     exit(1);
  607. }
  608. #endif
  609.  
  610. /* END CODE */
  611.